package likou.offer;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/16  12:23
 */
public class _32_3 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        treeNode.left=new TreeNode(9);
        treeNode.right=new TreeNode(20);
        treeNode.right.left=new TreeNode(15);
        treeNode.right.right=new TreeNode(7);
        System.out.println(levelOrder(treeNode));
    }
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> daan = new ArrayList<>();
        List<Integer> one = new ArrayList<>();
        Deque<TreeNode> nodesA = new LinkedList<>();
        Deque<TreeNode> nodesB = new LinkedList<>();
        if(root==null){
            return daan;
        }
        one.add(root.val);
        daan.add(one);
        nodesA.push(root);
        boolean p = false;
        while(true){
            one = new ArrayList<>();
            while(nodesA.size()!=0){
                TreeNode node = nodesA.pop();
                if(p){
                    if(node.left!=null){
                        nodesB.push(node.left);
                        one.add(node.left.val);
                    }
                    if(node.right!=null){
                        nodesB.push(node.right);
                        one.add(node.right.val);
                    }
                }else{
                    if(node.right!=null){
                        nodesB.push(node.right);
                        one.add(node.right.val);
                    }
                    if(node.left!=null){
                        nodesB.push(node.left);
                        one.add(node.left.val);
                    }
                }
            }
            nodesA = nodesB;
            nodesB = new LinkedList<>();
            if(nodesA.size()==0){
                break;
            }
            daan.add(one);
            p = !p;
        }
        return daan;
    }
}
